package cn.dlc.com.symboltable;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/**
 * @author 邓立川
 * @date 2021/3/21 16:38
 * @desc 顺序表
 */

@Data
public class OrderSymbolTable<Key extends Comparable<Key>, Value>{

    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    private class Node<Key, Value> {
        private Key key;
        private Value value;
        private Node<Key, Value> next;
    }

    private Node<Key, Value> head;
    private int num;

    public OrderSymbolTable(){
        this.head = new Node<>(null,null,null);
        this.num = 0;
    }

    public int size(){
        return this.num;
    }

    // 获取对应key的元素
    public Value get(Key key) {

        Node<Key,Value> node = head;

        for (int i = 0; i < this.num; i++) {
            node = node.getNext();
            if(key.equals(node.getKey())) {
                // 找到这个key
                return node.getValue();
            }
        }
        return null;
    }

    // 添加()
    public void put(Key key, Value value) {

        Node<Key,Value> node = head;

        // 记录首节点
        Node<Key,Value> before = null;

        while(node.getNext() != null) {

            if(key.compareTo(node.getKey()) > 0) {

                // 记录前一个节点
                before = node;
                // 添加的key比当前节点大，继续往后走
                node = node.getNext();

            } else if(key.compareTo(node.getKey()) < 0){
                // 添加的key小于当前node，那么需要添加在当前节点的前一个节点后面
                Node<Key, Value> newNode = new Node<>(key, value, node);
                before.setNext(newNode);
                this.num++;
                break;
            } else {
                // 相等的情况下
                node.setValue(value);
                break;
            }
        }
    }

    //
    public Value delete(Key key) {
        Node<Key,Value> node = head;

        while(node.getNext() != null) {
            node = node.getNext();
            // 获取下一个节点进行比较，如果是相同的
            if(key.equals(node.getKey())) {
                // 如果是相同的，那么就是要删掉这个
                // 我们直接指向这个几点的下一个节点
                node.setNext(node.getNext().getNext());
                this.num--;

                return node.getValue();
            }
        }

        return null;
    }
}
